package com.bear.线性结构.单项环形表;

/**  单项环形表----约瑟夫问题
 * <简述>  一个对象赋值给另一个对象，另一个对象可以改变自己的结构，但是如果改变自己的值，那么一个对象也会改变，这是因为
 * 他们指向内存的值的内存地址是同一个
 * <详细描述>
 *
 * @author LiuShanshan
 * @version $Id$
 */
public class Josepfu {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        // 添加a
        for(int i = 1; i<=4; i++){
            circleSingleLinkedList.add(new Boy(i));
        }
        // ==============查询=============
        System.out.println(" ==============查询=============");
        circleSingleLinkedList.show();
        // =============取出数据===============
        System.out.println("=============取出数据===============");
        circleSingleLinkedList.delete(1,2);
    }
}

class CircleSingleLinkedList{
    private Boy first = null;

    // 增
    public void add(Boy needBoy){
        if(first == null){
            first = needBoy;
            first.next = first;
        }
        // 给first后面增加数据
        Boy cusboy = first.next;
        while (true){
            if(cusboy.next == first){
                needBoy.next = first;
                cusboy.next = needBoy;
                break;
            }
            cusboy = cusboy.next;
        }
        System.out.println("添加成功");
    }

    // 出圈
    /**
     *<简述>
     *<详细描述>
     * @author Liushanshan
     * @param startNo  从哪条数据开始
     * @param nums   间隔几个数据进行取出
     * @return void
    */
    public void delete(int startNo, int nums){
        // 判断当前first是否为空

        // 开始取出，需要cub(当前辅助节点); later（cub只有的一个节点）
        Boy later = first;
        // 给later赋值为first的最后一个值
        while(true){
            if(later.next == first){
                break;
            }
            later = later.next;
        }
        // 开始位置为nums-1  ,确认开始循环的位置
        for (int i = 0; i < startNo - 1;  i++){
            first = first.next;
            later = later.next;
        }

        // 开始循环，每次循环次数为nums-1
        while (true){
            // 退出
            if(later == first){
                break;
            }
            for(int j = 0; j < nums -1; j++){
                first = first.next;
                later = later.next;
            }
            // 要出圈的小孩
            System.out.printf("\n要出去的数据：%s", first);
            // 因为已经出圈了，所以将later里面的next设置为first.next
            first = first.next;
            later.next = first;
        }
        System.out.printf("\n最后一个数据为：%s", later);
    }

    // 改 改变里面的数据最简单，不实现

    //查
    public void show(){
        // 判断first是否为空
        if(first == null){
            System.out.println("数据为空，请添加数据");
            return;
        }
        // 循环查询，结束语句为cub.next = first
        Boy cub = first;
        while (true){
            if(first.next == first){
                System.out.printf("当前只有一个数据为：%s", first);
                break;
            }
            if(cub.next == first){
                break;
            }
            System.out.printf("\n开始打印数据：%s", cub);
            cub = cub.next;
        }
        System.out.printf("\n最后一个数据为：%s", cub);
    }

}

class Boy{
    public int no;
    public Boy next;

    Boy(int no){
        this.no = no;
    }

    @Override
    public String toString() {
        return "Boy{" +
                "no=" + no +
                '}';
    }
}
